[LnOI2019]-加特林轮盘赌

概率与期望

有意思的题（我不会概率所以它超有意思（

比较妙的通过“环”的性质，化无限为递推。设 $f[n, k]$ 表示长度为 $n$ 的环中第 $k$ 个人唯一幸存的概率，那么有 $f[n, k] = p0 \times f[n - 1, k - 1] + (1 - p0) \times f[n, k - 1]$, 特别的 $f[n, 1] = (1 - p0) \times f[n, n]$

这玩意作为 dp 有后效性，想到消元。暴力消元炸没了，但我们发现假设前 $i - 1$ 行都算出来了，第 $i$ 行所有 $f[i, j]$ 只与 $f[i, 1]$ 有关，于是想到经典套路：表示成 $a \times f[i, 1] + b$ 的形式，$\sum\limits_{j = 1}^i f[i, j] = 1$，解出 $f[i, 1]$。

$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 1e4 + 10;
double p0, f[2][N];
int n, K, cur = 1, lst;

int main() {
    cin >> p0 >> n >> K;
    if (!p0) {
        puts(n == 1 ? "1" : "0"); return 0;
    }
    f[1][1] = 1;
    rep(i, 2, n) {
        lst = cur; cur ^= 1;
        double a = 1, A = 0, b = 0, B = 0;
        rep(j, 2, i) {
            a *= (1 - p0);
            A += a;
            b = p0 * f[lst][j - 1] + (1 - p0) * b;
            B += b;
        }
        f[cur][1] = (1 - B) / (A + 1);
        rep(j, 2, i)
            f[cur][j] = p0 * f[lst][j - 1] + (1 - p0) * f[cur][j - 1];
    }
    printf("%.8lf\n", f[cur][K]);
    return 0;
}

还有一种方法利用等比数列求和公式。设当前轮 $f[i]$ 表示 $i$ 唯一存活的概率，$g[i]$ 表示 $i$ 被打死的概率，$g[i] = (1 - p0)^{i - 1} p (\sum\limits_{j = 0}^{\infty} ((1 - p)^n)^i) = \frac{(1 - p)^{i - 1}}{1 - ((1 - p)^n)^i}$，然后每打死一个人就得到一个新的局面。